package com.yin.algorithms;

import com.yin.Sort;
import com.yin.Util;

public class ShellSort implements Sort {

    @Override
    public void sort(int[] arr) {

        //每一次的间隔
        for(int inc = arr.length >> 1; inc > 0; inc = inc >> 1) {

            //每次的间隔
            for(int i = inc; i < arr.length; i++) {

                for(int j = i; j >= inc; j -= inc) {

                    if(arr[j] < arr[j - inc]) {

                        Util.swap(arr, j, j - inc);

                    }

                }

            }

        }
    }
}
